Polar codes, proposed by E. Arikan in “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,” IEEE Transactions on Information Theory, vol. 55, pp. 3051-3073, July 2009 (hereinafter “Arikan”), are the first class of constructive coding schemes that are provable to achieve the symmetric capacity of the binary-input discrete memoryless channels under a low-complexity successive cancellation (SC) decoder. However, the finite-length performance of polar codes under SC is not competitive compared to other modern channel coding schemes such as low-density parity-check (LDPC) codes and Turbo codes. Later, a SC list (SCL) decoder was proposed by I. Tal and A. Vardy in “List Decoding of polar codes,” Proceedings of IEEE Symp. Inf. Theory, pp. 1-5, 2011 (hereinafter “Tal”), which can approach the performance of the optimal maximum-likelihood (ML) decoder. By concatenating simple Cyclic Redundancy Check (CRC) coding, it was shown that the performance of concatenated polar codes is competitive with that of well-optimized LDPC and Turbo codes. As a result, polar codes are being considered as a candidate for future wireless communication systems, such as 5G.
The main idea of polar coding is to transform a pair of identical binary-input channels into two distinct channels of different qualities, one better and one worse than the original binary-input channel. By repeating such a pair-wise polarizing operation on a set of 2M independent uses of a binary-input channel, a set of 2M “bit-channels” of varying qualities can be obtained. Some of these bit channels are nearly perfect (i.e., error free) while the rest of them are nearly useless (i.e., totally noisy). The point is to use the nearly perfect channel to transmit data to the receiver while setting the input to the useless channels to have fixed or frozen values (e.g., 0) known to the receiver. For this reason, those input bits to the nearly useless and the nearly perfect channel are commonly referred to as frozen bits and non-frozen (or information) bits, respectively. Only the non-frozen bits are used to carry data in a polar code.
Wireless broadband systems require flexible and adaptive transmission techniques because they operate in the presence of time-varying channels. For such systems, hybrid automatic repeat request based on incremental redundancy (HARQ-IR) schemes are often used, where parity bits are sent in an incremental fashion depending on the quality of the time-varying channel. IR systems require the use of rate-compatible punctured codes. According to the rate requirement, an appropriate number of coded bits are sent by the transmitter during the first transmission or subsequent retransmissions. Here, the set of coded bits of a higher rate code should be a subset of the set of coded bits of a lower rate code. In HARQ-IR systems, therefore, if the receiver fails to decode at a particular rate, it only needs to request additional coded bits to be transmitted in subsequent retransmissions by the transmitter. There has been extensive research on the construction of rate-compatible Turbo codes and LDPC codes. However, there is relatively few research done on rate-compatible polar codes.
FIG. 1 illustrates an example of polar code structure in a first transmission in HARQ incremental redundancy. More particularly, FIG. 1 illustrates the structure of a length-8 polar code. In the first transmission illustrated in FIG. 1, six out of eight bit channels of the length-8 polar code are loaded with data (non-frozen or information bits u0 through u5) while the rest are frozen (assigned a value of zero, which is known to the receiver), giving an overall code rate of ¾.
In both S. Hong, D. Hui, I. Maric, “Capacity Achieving Rate-Compatible Polar Codes,” Proc. ISIT, Bacelona, July 2016 (hereinafter “Hong”) and B. Li, D. Tse, K. Chen, H. Shen, “Capacity-Achieving Rateless Polar Codes,” Proc. ISIT, Bacelona, July 2016, a new class of rate-compatible polar codes was introduced to allow HARQ-IR retransmissions. For HARQ schemes that adopt this class of codes, each transmission (or retransmission) uses a separate polar code (with its own associated polar encoder) to generate a separate code block. A portion of non-frozen bits (e.g., a portion of non-frozen bits u0 through u5 in the example of FIG. 1) used in each of the previous transmissions are aggregated, re-encoded and transmitted in a subsequent retransmission. The amount of non-frozen bits taken from each previous transmission to form the new retransmission is determined in such a way that each of the previous (re-)transmissions would result in the same effective (lowered) coding rate if all subsequent transmissions are decoded successfully, and the decoded bits are used as frozen bits.
The aforementioned class of rate-compatible polar codes can be illustrated by an example using the three transmissions illustrated in FIGS. 1-3. As noted above, in the first transmission illustrated in FIG. 1, six out of the eight bit channels of a length-8 polar code are loaded with data while the rest are frozen, giving an overall code rate of ¾. If the receiver fails to decode the six information bits (u0 through u5), another length-8 polar code may be used to re-transmit the least reliable bits, which in the example of FIG. 1 are u3, u4, and u5. This first retransmission illustrated in FIG. 2, described below.
FIG. 2 illustrates an example of polar code structure in a second transmission (i.e., first retransmission) in HARQ incremental redundancy. If the receiver fails to decode the six information bits in the first transmission, another length-8 polar code such as the one illustrated in FIG. 2 may be used to re-transmit the three least reliable bits (u3, u4, u5). In the example of FIG. 2, the code rate in the 2nd code block is ⅜. Thus, the effective code rate of the 1st code block in the first transmission of FIG. 1 is also reduced from ¾ to ⅜ if the bits (u3, u4, u5) are successively decoded by the receiver from the 2nd code block and used as frozen bits to decode the first code block. If the receiver fails again to decode the 2nd transmission (i.e., first retransmission) of FIG. 2, the least reliable bit of the 2nd transmission, which in the example of FIG. 2 is u3, and the next least reliable bit u2 of the 1st transmission in the example of FIG. 1 (assuming not all data bits in the 2nd transmission have been successively decoded) are retransmitted using another length-8 polar code.
FIG. 3 illustrates an example of polar code structure in a third transmission (i.e., second retransmission) in HARQ incremental redundancy. If the receiver fails again to decode the second transmission (i.e., first retransmission) of FIG. 2, the least reliable bit of the 2nd transmission, which in the example of FIG. 2 is u3, and the next least reliable bit u2 of the 1st transmission in the example of FIG. 1 (assuming not all data bits in the 2nd transmission has been successively decoded) are retransmitted using another length-8 polar code such as the one illustrated in the example of FIG. 3. In this case, the effective code rates of all three code blocks of the three transmissions are all reduced to from ⅜ to ¼, assuming that all data bits in subsequent retransmissions are successively decoded and used as frozen bits in corresponding previous transmissions.
A method of successively decoding over multiple transmissions was also proposed in Hong. In this method, a decoder first decodes the most recent code block in the last retransmission and then uses the decoded (hard) bits as frozen bits to decode the previous (re)transmission until the first transmission is decoded. It can be shown that this simple decoding method achieves the aggregated capacity of all retransmissions.
Although the aforementioned successive decoding method over multiple transmissions achieves capacity, the decoding method is suboptimal in terms of block error performance. The reasons for this are twofold. First, decoding of code blocks of subsequent retransmissions does not take into account the information contained in the previous transmissions. As a result, the block error performance is limited by the block length of each individual transmission and does not benefit from the sum block length over all transmissions. Second, exchange of hard bits between one code block and another does not account for the reliability of the decoded information (non-frozen) bits.